The present invention relates to computer systems and in particular to graphic processing systems which graphically represent or render on a display surface objects defined in an object coordinate system.
Methods for rendering object coordinate system data into screen coordinate system data (screen space data) have been known for some time. A comprehensive description of a known method can be found in the book entitled xe2x80x9cComputer Graphics, (Pinciples and Practicexe2x80x9d, by Foley, van Dam, Feiner, Hughes, published by Addison-Wesley Publishing Company, ISBN 0-201-84840-6. Normally objects are defined by triangles in an object coordinate system or object space. A triangle is defined by its three vertices P1, P2, P3. In the case of a three-dimensional graphic application, each point in the three-dimensional coordinate system requires three coordinate values. The origin of the three-dimensional rectangular coordinate system in the object space or object coordinate system can be chosen at random. If the object to be represented is a sphere, for example, the origin of the object coordinate system is normally located at the centre of the sphere. The representation in the object coordinate system is thus defined from the outset and is independent of an observer standpoint.
An observer should now be able to move through space so as to be able to observe the surfaces defined in the object coordinate system, and thus objects, from his particular standpoint. A simple example should make this clear. Consider a house which has been specified in object coordinates. An observer should now be able to approach this house from e.g. the garden gate, in which case it is clear that he can then only see the facade but not any objects inside the house. Furthermore the observer can only see one side of the house wall, the visible side of the house call being of course the outer side if he is outside the house and the inner wall of a room if he is inside the house. The object coordinate system origin could e.g. be located on the ground floor, so that the cellar of the house will have negative y-coordinates in the object coordinate system while the first floor will have positive y-coordinates. It is therefore necessary to process the polygons, and thus triangles, specified xe2x80x9cabsolutelyxe2x80x9d in the object coordinate system in order to represent only what the observer sees on a screen. In addition it is necessary to light or shade the objects in the house in three dimensions. While the light source, e.g. the sun or a lamp in a room, may here be fixed absolutely in object coordinates, the observer will see different lit objects depending on his standpoint.
FIG. 4 shows a flowchart of a known method for rendering object coordinate system data so as to be able to display them on a monitor. Such a method is shown in J. D. Foley, A. Van Dam et al., xe2x80x9cComputer Graphicsxe2x80x9d, Addison-Wesley, 1996, FIG. 18.3.3.
In a first step 100 the object coordinate system data are transformed into an eye coordinate system or eye space, in which necessary lighting calculations 200 are performed. After the lighting 200 in the eye coordinate system a perspective projection is preferably performed so as to obtain clip coordinates or clip-space coordinates from the original object coordinates. After clipping 300 in the clip coordinate system, the homogeneous clip coordinates are dehomogenized.
In a first step 100 the object coordinate system data are transformed into an eye coordinate system or eye space, in which necessary lighting calculations 200 are performed. After the lighting 200 in the eye coordinate system a perspective projection is preferably performed so as to obtain clip coordinates or clip-space coordinates from the original object coordinates. After clipping 300 in the clip coordinate system, the homogeneous clip coordinates are dehomogenized.
The position of a triangle in the object coordinate system is normally represented redundantly in that the three coordinates of each vertex of the triangle in the coordinate system each has a respective scaling factor assigned to it. In accordance with the technical terminology, an unambiguous representation of points is termed an inhomogeneous representation, whereas an overdetermined or redundant representation of points is termed a homogeneous representation of these points. If a point on a two-dimensional surface is represented by means of two coordinates, this constitutes an inhomogeneous representation of the point. If a point on a two-dimensional surface is represented by means of three coordinates, this representation is overdetermined and is termed a homogeneous representation. By analogy thereto, a point in the three-dimensional coordinate system can be represented in an inhomogeneous way by its x-, y- and z-coordinates if the three-dimensional space is defined by a Cartesian coordinate system. A homogeneous representation of the point in the three-dimensional space is achieved by specifying 4 xe2x80x9ccoordinatesxe2x80x9d for the point in the three-dimensional space. The fourth coordinate w is by definition a scaling factor. A homogeneous x-, y-, z-coordinate is converted into an inhomogeneous x-, y- or z-coordinate by dividing by the scaling factor w. If a point in the space has inhomogeneous coordinates (1, 2, 3), its homogeneous representation could be (1, 2, 3, 1) or (2, 4, 6, 2), etc.
The advantage of the homogeneous representation of a point in the space is that all transformations which normally occur in a three-dimensional graphic processing or graphic pipeline (e.g. a translation, a rotation, a scaling and in particular a perspective projection) can be represented as a multiplication of the position of the point with a 4xc3x974 transformation matrix. The coordinates used in the steps 100, 200 and 300 are homogeneous coordinates, which are converted into inhomogeneous coordinates in the dehomogenization step 400. This dehomogenization is effected in a simple way by dividing the homogeneous x-, y-, z-values by the corresponding scaling factor w of this point. After dehomogenization, the talk is of coordinates in the screen coordinate system or screen space. The step 500 is then performed in the screen coordinate system. In this step triangles which do not have the desired orientation are culled. If two-sided lighting is employed, triangles with undesired orientation are not culled but are simply lit differently. The step 500 thus determines the type of lighting to be used for a triangle. In the case of a house where the outer wall is also the inner wall of a room, the outer wall is lit e.g. in yellow, if the house is painted yellow, while the inner wall of the room is lit up in white. Thus if an observer is outside the house, the graphic rendering method determines that only triangular surfaces which represent outer walls, i.e. which have a particular orientation, are to be displayed, while inner walls, i.e. triangular surfaces with opposite orientation, can be ignored. If there is only one type of lighting, the triangular surfaces whose orientation corresponds by definition to an interior orientation, are culled or, in the case of two-sided lighting, are provided with a type of lighting which discloses that what is involved here is a triangular surface which should describe the outer wall of a house.
It should be pointed out here that in the step 200 in the known method all the triangles are lit or both types of lighting are calculated for all triangles in the case of two-sided lighting, although half the triangles are culled again in the step 500 or one of the two types of lighting of a triangle is ignored when the triangles are subsequently displayed on a screen in a step 600.
As an alternative to the prior art described in FIG. 4, triangles can also be lit directly in the object coordinate system, whereupon the lit object coordinate surfaces are transformed directly into the clip coordinate system (clip space) without involving the eye coordinate system. This approach is favourable from the point of view of numerical considerations, since the lit object coordinates can be transformed into the clip coordinate system using a single matrix, this combined transformation matrix resulting from a matrix multiplication of the individual transformation matrices.
In the following the step 500 of culling triangles with undesired orientation is considered. First of all the orientation of a triangle is determined. FIG. 3 shows two triangles with different orientations. The orientation is determined by the sense of rotation, which results when the first vertex P1 is connected to the second vertex P2 and the second vertex P2 is then connected to the third vertex P3 and the third vertex P3 is then connected to the first vertex P1, as is represented by the arrows in FIG. 3. The left-hand triangle in FIG. 3 then exhibits an orientation out of the plane of the drawing, while the right-hand triangle has an orientation into the plane of the drawing.
It should be noted that this orientation is determined solely by the sequence of the vertices, i.e. can be chosen at will, since a triangle displayed on a screen and having a clockwise orientation cannot be distinguished from a corresponding triangle with a counterclockwise orientation if the triangles have been lit in the same manner. It is therefore e.g. possible, in the example of the house which has been presented, to provide all the outer surfaces of the house with an orientation according to the left-hand triangle of FIG. 3, while all the inner surfaces of the house have an orientation according to the right-hand triangle of FIG. 3. When a graphic rendering method has recognized that an observer is outside the house, it can immediately cull all the triangles with the other orientation since they are, on the basis of their definition, interior triangles.
The determination of the orientation of the surface of a triangle on a display surface thus plays an important role. It is this that determines whether the observer is looking at the front or the back of the triangle. From geometry it is known how to calculate the orientation of a triangle which is spanned by three points in space. This orientation is determined by the sign of the z-coordinate of the normal vector to the surface of the triangle. If the triangle is skewed in space, the normal vector will have a component in the x-direction, a component in the y-direction and a component in the z-direction. If the orientation of a triangle relative to an axis on which the observer finds himself is required, only the component of the normal vector parallel to this axis is needed. In graphic rendering systems the horizontal extension of the screen will normally be parallel to the x-axis and the vertical extension of the screen will normally be parallel to the y-axis. The z-axis, which is perpendicular to the screen or display surface, is then the observation axis. Thus what is needed is the orientation of a triangle relative to this observation axis.
This is given by the z-component of the vector product of the 2 directional vectors which result when the position of one vertex of a triangle is subtracted from the other two vertices. This relationship can be expressed in equational form as follows:                     a        =                              [                                          (                                                      v                    2                                    -                                      v                    1                                                  )                            xc3x97                              (                                                      v                    3                                    -                                      v                    1                                                  )                                      ]                    z                                    (        1        )                                          xe2x80x83                ⁢                  =                                                    (                                                      x                    2                                    -                                      x                    1                                                  )                            ⁢                              (                                                      y                    3                                    -                                      y                    1                                                  )                                      -                                          (                                                      y                    2                                    -                                      y                    1                                                  )                            ⁢                              (                                                      x                    3                                    -                                      x                    1                                                  )                                                                        (        2        )            
In this equation v1, v2 and v3 represent the vectors from the origin of the coordinate system to the three vertices of the triangle, i.e. to P1, P2 and P3. P1 is given by (x1, y1), P2 is given by (x2, y2) and P3 is given by (x3, y3). The point coordinates used in the equations (1) and (2) are inhomogeneous coordinates. Unfortunately, however, inhomogeneous coordinates are obtained only after the dehomogenization 400, since the operations performed previously must be performed in homogeneous coordinates, mainly for numerical reasons. This is also the reason why all the existing triangles are lit in step 200, after which each second triangle is culled in step 500, as a result of which a known graphic pipeline expends a great deal of unnecessary processor effort, since in general 50% of the computational effort for calculating the lighting is discarded again further on in the graphic pipeline.
It should be noted that a dehomogenization of the homogeneous coordinates cannot be executed prior to the lighting step since clipping must be performed in homogeneous coordinates. A prerequisite for correct clipping is, however, that the lighting operations are performed previously so as to make colour interpolation possible. These constraints are known to experts in the field and are thus not pursued further here.
To summarize, it can be stated that in a known graphic pipeline, regardless of whether the lighting is performed in the object coordinate system or in the eye coordinate system, there is a considerable unnecessary extra outlay since triangles which are later culled are first lit or because both types of lighting are calculated for each triangle whereas only one type of lighting is later displayed.
EP 0 740 272 A2 discloses a method and a device for the fast rendering of three-dimensional objects. Triangles are originally specified in a model space, which is the reference coordinate system for the graphic data which are finally to be displayed on a screen, which is described by a device space, i.e. by a screen coordinate system. Before transforming the triangles from the model space into the screen space, in which the lighting and clipping take place, the orientation of the triangles with respect to an observation standpoint is determined. To this end a vector, termed the eye vector, is formed by joining a point of the triangle in the model space to the observation point. The normal vector for the triangle is then either read or calculated and the scalar product of the eye vector and the normal vector for the triangle is calculated. This scalar product is calculated in the model coordinate system. Its sign indicates whether a triangle is directed away from the observer or towards the observer. This property of the triangle is stored in a list, which is accessed when the triangles are subsequently rendered so that if triangles which are directed away from the observer standpoint are culled, only those triangles which are directed towards the observer have to be transformed. In other words, only those triangles whose list entry indicates an orientation towards the observation standpoint are transformed from the model coordinate system into the device coordinate system and are there lit and clipped before being displayed on a screen after some further steps.
It is the object of the present invention to provide a more efficient concept for the graphic representation of a triangle.
In accordance with a first aspect of the present invention, this object is achieved by a device for the graphic representation on a display surface of an object defined by a plurality of triangles which are respectively specified by three points in homogeneous object coordinates, comprising: a device for transforming the homogeneous object coordinates of the plurality of triangles into homogeneous clip coordinates of a clip coordinate system with an observer standpoint located on an observation axis which is perpendicular to the display surface; a device for determining the position of the observer standpoint in relation to each of the plurality of triangles by determining the orientation of each triangle of the plurality of triangles in the clip coordinate system with respect to the observer standpoint using the homogeneous clip coordinates of the plurality of triangles, where the device for determining the position of the observer standpoint in relation to each of the plurality of triangles is designed to execute the following equation to determine the orientations of the triangles:
axe2x80x2=w1(I2y3xe2x88x92I3y2)+w2(I3y1xe2x88x92I1y3)+w3(I1y2xe2x88x92I2y1)
where (x1, y1, w1), (x2, y2, w2) and (x3, y3, w3) are homogeneous clip coordinates of the three vertices of the triangle and where the sign of axe2x80x2 indicates which of two orientations with respect to the observer standpoint each triangle has; a device for marking the position of the observer standpoint in relation to each triangle of the plurality of triangles in association with the homogeneous object coordinates of the plurality of triangles; and a device for processing the triangles specified in the object coordinates using the marked position of the observer standpoint in relation to each triangle so as to graphically represent the object on the display surface, where the device for processing is designed to cull the triangles specified in the object coordinate system which are directed away from the observer standpoint.
In accordance with a second aspect of the present invention, this object is achieved by a method for the graphic representation on a display surface of an object defined by a plurality of triangles which are respectively specified by three points in homogeneous object coordinates, comprising the following steps: transforming the homogeneous object coordinates of the plurality of triangles into homogeneous clip coordinates of a clip coordinate system with an observer standpoint located on an observation axis which is perpendicular to the display surface; determining the position of the observer standpoint in relation to each of the plurality of triangles by determining the orientation of each triangle of the plurality of triangles in the clip coordinate system with repect to the observer standpoint using the homogeneous clip coordinates of the plurality of triangles, where the device for determining the position of the observer standpoint in relation to each of the plurality of triangles is designed to execute the following equation to determine the orientations of the triangles:
axe2x80x2=w1(I2y3xe2x88x92I3y2)+w2(I3y1xe2x88x92I1y3)+w3(I1y2xe2x88x92I2y1)
where (x1, y1, w1), (x2, y2, w2) and (x3, y3, w3) are homogeneous clip coordinates of the three vertices of the triangle and where the sign of axe2x80x2 indicates which of two orientations with respect to the observer standpoint each triangle has; marking the position of the observer standpoint in relation to each triangle of the plurality of triangles in association with the homogeneous object coordinates of the plurality of triangles; and processing the triangles specified in the object coordinates using the marked position of the observer standpoint in relation to each triangle so as to graphically represent the object on the display surface, where the step of processing comprises the culling of the triangles specified in the object coordinate system which are directed away from the observer standpoint.
The present invention is based on the finding that the culling of triangles or the definitive establishment of the type of lighting for two-sided lighting must be performed before lighting in order to avoid unnecessary lighting calculations. If the culling of triangles is already performed in clip coordinates prior to clipping, then it is also possible when clipping to economize on clipping operations, which in the prior art are also performed on triangles which are subsequently culled and are not displayed on a screen. As can be seen from FIG. 4, culling a triangle prior to lighting or determining the type of lighting for two-sided lighting requires that the determination of the orientation of a triangle be performed using homogeneous coordinates. Until now, however, there has only been an equation for inhomogeneous coordinates.
To enable the determination of the orientation of a triangle to be performed in homogeneous coordinates, the following equation is proposed:
axe2x80x2=w1(I2y3xe2x88x92I3y2)+w2(I3y1xe2x88x92I1y3)+w3(I1y2xe2x88x92I2y1)
As can be seen from this equation, homogeneous coordinates (x, y, w) are employed, which are coordinates in the clip coordinate system, where the sign of axe2x80x2 indicates the orientation of the surface of a triangle defined by a point P1, a point P2 and a point P3. In the equation it is assumed that in the clip coordinate system the xy-plane of the clip coordinates is parallel to the display surface while an observer axis, relative to which the orientation of the surface of the triangle is determined, is perpendicular to the display surface, i.e. perpendicular to the xy-plane of the clip coordinate system.
The previous equation thus enables the orientation of a triangle to be determined before it is clipped. Consequently, according to the present invention, triangles with a particular orientation are culled before they have to be lit and clipped. In the case of two-sided lighting the triangles are, according to the present invention, now lit only on the side which is directed towards the observer. This provides the possibility of a more efficient graphic pipeline, wherein culling of triangles with a particular orientation or the side determination for two-sided lighting is carried out before lighting and clipping are necessary.
According to the present invention, therefore, the position of the observer standpoint in relation to each of the plurality of triangles is established at the start of a graphic pipeline by determining the orientation of each triangle in clip-space coordinates. The position of the observer standpoint is then marked in relation to each triangle in association with the homogeneous object coordinates of the plurality of triangles in such a way that the triangles defined in object coordinates can, after marking, be processed in the known manner but with the profound difference from the prior art that only those triangles whose orientation is such that they are to be displayed have to pass through the complete graphic pipeline.
In the case of one-sided lighting, marking ensures that only those triangles which are directed towards the observer standpoint are selected from all the triangles in the object space and these are then lit, transformed into the clip space and clipped.
In the case of two-sided lighting, the type of lighting is, according to the present invention, determined before lighting and possibly before the transformation into the eye coordinate system, in such a way that only one lighting operation has to be performed for each triangle, namely for that side of the triangle which has to be used for the display, i.e. that side of the triangle which is directed towards the observer.
Concerning the culling of triangles of a particular orientation, the method and devices of the present invention provide the possibility that, seen statistically, only half of all triangles have to be lit and clipped, which results in an increase in efficiency of 50% as regards lighting and clipping. In the case of two-sided lighting, only one lighting calculation has to be performed for each triangle instead of two lighting calculations for each triangle as On the prior art, which also, seen statistically, brings with it an increase in performance of 50% for the lighting processor.
From the short description of the present invention given above it is clear that the further steps for representing a triangle after orientation determination and culling or single-sided lighting are not essential to the present invention and can be carried out in any known way. Thus lighting can take place optionally in the object coordinate system or, after a transformation into the eye coordinate system, in this coordinate system.